package com.note.feng.leetcode.algorithms.easy.five;

import java.util.ArrayList;
import java.util.HashMap;
import java.util.List;
import java.util.Map;

public class FiveHundredNinetyNine {
    /**
     * 599 两个列表的最小索引总和
     * 假设 Andy 和 Doris 想在晚餐时选择一家餐厅，并且他们都有一个表示最喜爱餐厅的列表，每个餐厅的名字用字符串表示。
     *
     * 你需要帮助他们用最少的索引和找出他们共同喜爱的餐厅。 如果答案不止一个，则输出所有答案并且不考虑顺序。 你可以假设答案总是存在。
     *
     * 示例 1:
     *
     * 输入: list1 = ["Shogun", "Tapioca Express", "Burger King", "KFC"]，
     * list2 = ["Piatti", "The Grill at Torrey Pines", "Hungry Hunter Steakhouse", "Shogun"]
     * 输出: ["Shogun"]
     * 解释: 他们唯一共同喜爱的餐厅是“Shogun”。
     * 示例 2:
     *
     * 输入:list1 = ["Shogun", "Tapioca Express", "Burger King", "KFC"]，list2 = ["KFC", "Shogun", "Burger King"]
     * 输出: ["Shogun"]
     * 解释: 他们共同喜爱且具有最小索引和的餐厅是“Shogun”，它有最小的索引和1(0+1)。
     *  
     * 提示:
     *
     * 1 <= list1.length, list2.length <= 1000
     * 1 <= list1[i].length, list2[i].length <= 30 
     * list1[i] 和 list2[i] 由空格 ' ' 和英文字母组成。
     * list1 的所有字符串都是 唯一 的。
     * list2 中的所有字符串都是 唯一 的。
     *
     * 来源：力扣（LeetCode）
     * 链接：https://leetcode.cn/problems/minimum-index-sum-of-two-lists
     */
    /**
     * 解法：哈希
     * 先将 list1 的值存入 map 中，字符串为 key，下标为 value
     * 再遍历 list2，若 map 中存在这个 key，计算下标总和是否小于当前值
     * 若小于，则清空 list，并存入当前 key
     * 若等于，则存入当前 key
     * @param list1
     * @param list2
     * @return
     */
    public String[] findRestaurant(String[] list1, String[] list2) {
        Map<String, Integer> map = new HashMap<>();
        for (int i = 0; i < list1.length; i++) {
            map.put(list1[i], i);
        }
        List<String> list = new ArrayList<>();
        int min = list1.length + list2.length;
        for (int i = 0; i < list2.length; i++) {
            if(map.containsKey(list2[i])){
                int j = map.get(list2[i]) + i;
                if(min > j){
                    min = j;
                    list.clear();
                    list.add(list2[i]);
                }else if(min == j){
                    list.add(list2[i]);
                }
            }
        }
        return list.toArray(new String[list.size()]);
    }
}
